package cn.fansunion.leecode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树的中序遍历
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 * @author wen.lei@brgroup.com
 *
 *         2022-1-20
 */
public class BinaryTreeInorderTraversal {

    /**
     * 给定一个二叉树的根节点 root ，返回它的 中序 遍历
     * @param root
     * @return
     */
    public <T> List<T> inorderTraversal(TreeNode<T> root) {
        List<T> nodeIdList = new ArrayList<>();
        inorderTraversal(nodeIdList, root);
        return nodeIdList;
    }

    private <T> void inorderTraversal(List<T> nodeIdList, TreeNode<T> root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            inorderTraversal(nodeIdList, root.left);
        }
        nodeIdList.add(root.val);
        if(root.right!=null) {
            inorderTraversal(nodeIdList, root.right);
        }
    }

}
